package main.leetcode.clockin.Auguest;

import java.util.ArrayList;
import java.util.List;

/**
 * 679. 24 点游戏
 *
 * <p>你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
 *
 * <p>示例 1: 输入: [4, 1, 8, 7] 输出: True 解释: (8-4) * (7-1) = 24
 *
 * <p>示例 2: 输入: [1, 2, 1, 2] 输出: False
 *
 * <p>注意: 除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。 每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1,
 * 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。 你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。
 */
public class day22 {
    private boolean res;

    public static void main(String[] args) {
        System.out.println(new day22().judgePoint24(new int[] {4, 1, 8, 7}));
    }

    //    public boolean judgePoint24(int[] nums) {
    //        List<Double> list = new ArrayList<>();
    //        for (int num : nums) {
    //            list.add((double) num);
    //        }
    //        return dfs(list);
    //    }
    //
    //    private boolean dfs(List<Double> list) {
    //        int n = list.size();
    //        if (n == 1) {
    //            // 除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。
    //            // 在判断结果是否等于 24 时应考虑精度误差，这道题中，误差小于 10e−6 可以认为是相等。
    //            return Math.abs(list.get(0) - 24) <= 0.00001;
    //        }
    //        for (int i = 0; i < n; ++i) {
    //            for (int j = i + 1; j < n; ++j) {
    //                List<Double> tmp = new ArrayList<>(list);
    //                // 这里要注意先remove j，再remove i。不然会越界
    //                double a = tmp.remove(j);
    //                double b = tmp.remove(i);
    //                boolean res;
    //                tmp.add(a + b);
    //                res = dfs(tmp);
    //                tmp.set(tmp.size() - 1, a - b);
    //                res |= dfs(tmp);
    //                tmp.set(tmp.size() - 1, b - a);
    //                res |= dfs(tmp);
    //                tmp.set(tmp.size() - 1, a * b);
    //                res |= dfs(tmp);
    //                tmp.set(tmp.size() - 1, a / b);
    //                res |= dfs(tmp);
    //                tmp.set(tmp.size() - 1, b / a);
    //                res |= dfs(tmp);
    //                if (res) {
    //                    return true;
    //                }
    //            }
    //        }
    //        return false;
    //    }

    public boolean judgePoint24(int[] nums) {
        List<Double> list = new ArrayList<>();
        for (int num : nums) {
            list.add((double) num);
        }
        dfs(list);
        return res;
    }

    private void dfs(List<Double> list) {
        if (res) {
            return;
        }
        int n = list.size();
        if (n == 1) {
            // 除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。
            // 在判断结果是否等于 24 时应考虑精度误差，这道题中，误差小于 10e−6 可以认为是相等。
            res = Math.abs(list.get(0) - 24) <= 0.00001;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                List<Double> tmp = new ArrayList<>(list);
                double a = tmp.remove(j);
                double b = tmp.remove(i);
                tmp.add(a + b);
                dfs(tmp);
                if (res) {
                    return;
                }
                tmp.set(tmp.size() - 1, a - b);
                dfs(tmp);
                if (res) {
                    return;
                }
                tmp.set(tmp.size() - 1, b - a);
                dfs(tmp);
                if (res) {
                    return;
                }
                tmp.set(tmp.size() - 1, a * b);
                dfs(tmp);
                if (res) {
                    return;
                }
                tmp.set(tmp.size() - 1, a / b);
                dfs(tmp);
                if (res) {
                    return;
                }
                tmp.set(tmp.size() - 1, b / a);
                dfs(tmp);
                if (res) {
                    return;
                }
            }
        }
    }
}
